package MemorySearch;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * P322 零钱兑换
 * */
public class P322 {
    public static void main(String[] args) {
        int[] a={1,2,5};
        int n=11;

        P322Test01 p322Test01=new P322Test01();
        System.out.println(p322Test01.coinChange(a, n));


    }
}
class P322Test01{
    /**
     * 思路求解:
     * 求最值问题，优先想到动态规划，可以利用记忆化递归（自顶向上）或者动态规划（自底向上），
     * 动态规划：1.确定初始值，2.确定动态转移方程
     * */
    public int coinChange(int[] coins, int amount) {

        if(coins.length<=0){
            return -1;
        }

        //设置用来记录答案
        int[] dp=new int[amount+1];


        //找最小值，所以要初始化最大值
        Arrays.fill(dp, amount+1);
        //初始化,刚开始零中可能
        dp[0]=0;


        //结束条件amount被分配完
        //遍历所有
        for(int i=1;i<=amount;i++){
            //遍历货币值
            for(int coin:coins){
                if(i-coin<0){
                    continue;
                }
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }

        return dp[amount]==(amount+1)?-1:dp[amount];

    }
}

